/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-05-16
 * Time: 22:21
 */

import java.util.*;

/**
 * @Author 12629
 * @Description：
 */

public class BinaryTree {
    class TreeNode {
        public char val;
        public  TreeNode left;
        public  TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }


    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    static int num=0;
    //    public static TreeNode Creattree(String str){
//        TreeNode node;
//        char ch=str.charAt(num);
//        num++;
//        if(ch!='#'){
//            node=new TreeNode(ch);
//            node.left=Creattree(str);
//            node.right=Creattree(str);
//        }else{
//            node=null;
//        }
//        return node;
//    }
    // 前序遍历
    void preOrder(TreeNode root){
        if (root==null){
            return;
        }
        System.out.print(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
    // 中序遍历
    void inOrder(TreeNode root){
        if (root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val);
        inOrder(root.right);
    }
    // 后序遍历
    void postOrder(TreeNode root){
        if (root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val);
    }
    //    List<Integer> ret = new ArrayList<>();
//    public List<Integer> preorderTraversal(TreeNode root) {
//        if(root == null) return ret;
//        //System.out.print(root.val+" ");
//        ret.add(root.val);
//        preorderTraversal(root.left);
//        preorderTraversal(root.right);
//        return ret;
//    }
    int size(TreeNode root){
        if (root==null){
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }
    int getLeafNodeCount(TreeNode root){
        if (root==null){
            return 0;
        }
        if (root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }
    int getKLevelNodeCount(TreeNode root,int k){
        if (root==null){
            return 0;
        }
        if (k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+
                getKLevelNodeCount(root.right,k-1);
    }
    int getHeight(TreeNode root){
        if (root==null){
            return 0;
        }
        int leftnum=getHeight(root.left);
        int righttnum=getHeight(root.right);

        return (leftnum>righttnum?leftnum:righttnum)+1;
    }
    TreeNode find1(TreeNode root, char val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        if (find(root.left, val)!=null){
            return find(root.left,val);
        }
        if (find(root.right,val)!=null) {
            return find(root.right, val);
        }
        return null;
    }
    TreeNode find(TreeNode root, char val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        TreeNode lef=find(root.left,val);
        if (lef!=null){
            return lef;
        }
        TreeNode rig=find(root.right,val);
        if (rig!=null){
            return rig;
        }
        return null;
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q!=null||p!=null&&q==null){
            return false;
        }
        if(p==null&&q==null){
            return true;
        }
        if(p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null&&subRoot!=null||root!=null&&subRoot==null){
            return false;
        }
        if(root==null&&subRoot==null){
            return true;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;

    }
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        return getHeight(root)>0?true:false;
    }
    int getHeight1(TreeNode root){
        if (root==null){
            return 0;
        }
        int leftnum=getHeight(root.left);
        int righttnum=getHeight(root.right);
        if(leftnum<0||righttnum<0||Math.abs(leftnum-righttnum)>1){
            return -1;
        }

        return (leftnum>righttnum?leftnum:righttnum)+1;
    }
    public boolean isBalanced1(TreeNode root) {
        if(root==null){
            return true;
        }
        int vale=getHeight(root.left)-getHeight(root.right);
        if(Math.abs(vale)>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        if(leftTree == null && rightTree != null ||
                leftTree != null && rightTree == null ) {
            return false;
        }
        if(leftTree == null && rightTree == null) {
            return true;
        }
        if(leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)
                && isSymmetricChild(leftTree.right,rightTree.left);
    }
    void levelOrder(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode top=queue.poll();
            System.out.println(top.val);
            if (top.left!=null){
                queue.offer(top.left);
            }
            if (top.right!=null){
                queue.offer(top.right);
            }
        }
    }
    boolean isCompleteTree(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        TreeNode top=root;
        if (root!=null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()){
            TreeNode tmp=queue.poll();
            if(tmp!=null){
                queue.offer(tmp.left);
                queue.offer(tmp.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()){
            TreeNode emo=queue.poll();
            if (emo!=null){
                return false;
            }
        }
        return true;
    }
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if(root==null){
            return false;
        }
        stack.push(root);
        if(root==node){
            return true;
        }
        boolean inleft=getPath(root.left,node,stack);
        if (inleft==true) {
            return true;
        }
        boolean inright=getPath(root.right,node,stack);
        if (inright==true) {
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q){
        if(root==null){
            return null;
        }
        Stack<TreeNode> stack1=new Stack<>();
        getPath(root,p,stack1);
        Stack<TreeNode> stack2=new Stack<>();
        getPath(root,q,stack2);
        int size1=stack1.size();
        int size2=stack2.size();
        if (size1>size2){
            int size=size1-size2;
            while (size!=0){
                size--;
                stack1.pop();
            }
        }else {
            int size=size2-size1;
            while (size!=0){
                size--;
                stack2.pop();
            }
        }
        while (!stack1.isEmpty()&&!stack2.isEmpty()){
            TreeNode tmp1=stack1.pop();
            TreeNode tmp2=stack2.pop();
            if (tmp1==tmp2){
                return tmp1;
            }
        }
        return null;
    }
    public void preOrderNor(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        //把头结点root赋值给cur
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()) {
            //将左边的结点依次入栈
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val);
                cur = cur.left;
            }
            //左结点为null后，弹出遍历右树（右结点）
            TreeNode top = stack.pop();
            cur = top.right;
            //为null,则继续弹出左节点。
        }
    }
    public void inOrderNor(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            //弹出顺序即为中序遍历
            System.out.print(top.val);
            cur = top.right;
        }
    }
    public void postOrderNor(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        //prev来记录已打印过的结点
        TreeNode prev=null;
        while (cur!=null||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //栈顶的左边已为null;入为null且没被打印过，则弹出当前节点.
            //不为null，则遍历右树。不加prev程序会认为cur的右树未打印，会重复添右节点。
            TreeNode top = stack.peek();
            if (top.right!=null&&prev!=top.right){
                cur=top.right;
            }else {
                System.out.print(top.val);
                prev=top;
                stack.pop();
            }
        }
    }

}